package ljl.codetop;

import commons.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 操他妈上来就被难住了
 */
public class _662_max_width {

    static class solution_dfs {
        Map<Integer, Integer> level2IdMap = new HashMap<>();
        int max;
        public int widthOfBinaryTree(TreeNode root) {
            dfs(root, 1, 0);
            return max;
        }
        void dfs(TreeNode node, int id, int level) {
            if (node == null) return;
            if (!level2IdMap.containsKey(level)) level2IdMap.put(level, id);
            max = Math.max(max, id - level2IdMap.get(id) + 1);
            // 这个优化个人感觉不是很必要
            id = id - level2IdMap.get(level) + 1;
            dfs(node.left, id << 1, level + 1);
            dfs(node.right, id << 1 | 1, level + 1);
        }
    }

    static class solution_bfs {
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            Map<TreeNode,Integer> map = new HashMap<>();
            Queue<TreeNode> queue = new LinkedList<>();
            int max = 1;
            queue.offer(root);
            map.put(root,1);
            while (!queue.isEmpty()) {
                int start = map.get(queue.peek());
                int index = -1;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    index = map.get(node);
                    if (node.left != null) {
                        map.put(node.left, index << 1);
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        map.put(node.right, index << 1 | 1);
                        queue.offer(node.right);
                    }
                }
                max = Math.max(max, index - start + 1);
            }
            return max;
        }
    }
}
